The following are some notes taken during a lecture.
Propositions
- A proposition is a declarative sentence that is either true or false
- Examples:
- Neil Armstrong was a Purdue Alum. true
- Purdue Computer Science is in the Silicon Valley. false
- Purdue won the 2018 NCAA men’s basketball championship. false
- 1 + 0 = 1 true
- 0 + 0 = 2 false
- Examples that are not propositions:
- What is the temperature outside? 70
- Why did you not do your homework? string
- x + 1 = 2aa ..
Variables and Assignments
- Much as algebra is comprised of numbers and variables, propositional logic is comprised of truth values and propositional variables (p, q, r)
- Just as variables in algebra can take values (e.g., x = 15, y = 0), variables in propositional logic can be assigned truth values (e.g., p = True, q = False).
- A proposition that is always true is denoted by T and the proposition that is always false is denoted by F.
Compound Propositions
- Propositions, combined with connectives, can be used to build compound propositions.
- Logical Connectives are:
- Negation (NOT) ¬
- Conjunction (AND) ∧
- Disjunction (OR) ∨
- Implication →
- Biconditional ↔
Compound Propositions: Negation (¬)
- The negation of a proposition p is denoted by ¬p (read as NOT p). It `negates’ the truth value of the proposition and has this truth table.
| p | ¬p |
| T | F |
| F | T |
- Example: If p denotes the proposition “Purdue Computer Science is awesome.”, then ¬p denotes the proposition “It is not the case that Purdue Computer Science is awesome,” or simply “Purdue computer Science is not awesome”.
Conjunction (AND ∧ )
- The conjunction of propositions p and q is denoted by p ∧ q (read as p AND q) . Its truth table is:
| p | q | p ∧ q |
| T | T | T (only truth result) |
| T | F | F |
| F | T | F |
| F | F | F |
- Example: If p denotes “Purdue is in West Lafayette.” and q denotes “West Lafayette is cool.” then p ∧q denotes “Purdue is in West Lafayette and West Lafayette is cool.”
Disjunction (OR ∨ )
- The disjunction of propositions p and q is denoted by p ∨q (read as p OR q). It has the truth table:
| p | q | p ∨q |
| T | T | T |
| T | F | T |
| F | T | T |
| F | F | F (only truth result) |
- Example: If p denotes “I am at the lab.” and q denotes “I am at the gym.” then p ∨q denotes “I am at the lab or I am at the gym.”
Disjunction is Inclusive OR
- In English “or” has two distinct meanings – inclusive or, or exclusive or.
- “Inclusive Or” – In the sentence “Students who have taken CS1 or Math2 may take CS2,”. This sentence implies that students who have taken either of these classes, as well as those who have taken both of these classes may take CS2. This is called inclusive Or.
- Disjunction (or simply OR) in logic corresponds to inclusive Or.
- Stated otherwise, for p ∨q to be true, either one or both of p and q must be true.
Exclusive OR (XOR ⊕ )
- Consider the typical restaurant menu statement: Each entre comes with soup or salad. This means that one may get either a soup or a salad with their entre, but not both. This is called an exclusive Or.
- Exclusive Or is distinct from Inclusive Or.
- The logical connective corresponding to Exclusive Or (XOR) is ⊕.
- In p ⊕ q , one of p and q must be true, but not both.
- The truth table for ⊕ is:
| p | q | p ⊕q |
| T | T | F |
| T | F | T |
| F | T | T |
| F | F | F |
Implication
- Consider the english statement: If you score above 90% on the final, you will get an A. This is an example of an implication.
- If p and q are propositions, then p →q is a conditional statement or implication which is read as “if p, then q ” and has this truth table:
| p | q | p →q |
| T | T | T |
| T | F | F |
| F | T | T |
| F | F | T |
- Example: If p denotes “you score above 90% on the final” and q denotes “You get an A.” then p →q denotes “If you score above 90% on the final, you get an A.”
- In the implication p →q , p is called the hypothesis (antecedent or premise) and q is called the conclusion (or consequence).
- In an implication (e.g., p →q ) there may not be any connection between the antecedent and the consequent. The “meaning” of p →q depends only on the truth values of p and q.
- The following implications are legal, but would not make colloquial sense.
- “If the moon is made of green cheese, then I have more money than Bill Gates. ” F -> F = T
- “If the moon is made of green cheese then I am eight feet tall.” F -> F = T
- “If 1 + 1 = 3, then your grandma wears combat boots. F -> F = T
- One way to view the logical conditional is to think of it as an obligation or contract.
- “If you score above 90% on the final, then you will get an A.”
- If you score above 90% on the final and you do not get an A, the professor would have reneged on his contract (i.e., the implication does not hold). This corresponds to the case where p is true and q is false. In this case, p →q is false.
- It is also important to note that if you get an A, it may or may not be the case that you score above 90% on the final.
Different Ways of Expressing p →q (Implications)
if p, then q p implies q
if p, q p only if q
q unless ¬p q when p
q if p
q whenever p p is sufficient for q
q follows from p q is necessary for p
a necessary condition for p is q
a sufficient condition for q is p
Converse, Contrapositive, and Inverse
- From p →q we can form new conditional statements .
q →p is the converse of p →q
¬q → ¬ p is the contrapositive of p →q
¬ p → ¬ q is the inverse of p →q - Example: Find the converse, inverse, and contrapositive of “It is raining is a sufficient condition for my not going to town.”
- Solution: p corresponds to “It is raining” and q to “my not going to town”, and the example corresponds to the implication p →q.
- converse: If I do not go to town, then it is raining. (q →p)
- inverse: If it is not raining, then I will go to town.(¬ p → ¬ q)
- contrapositive: If I go to town, then it is not raining. (¬q → ¬ p )
Biconditional (if and only if)
- If p and q are propositions, then we can form the biconditional proposition p ↔q , read as “p if and only if q .” The biconditional p ↔q denotes the proposition with this truth table:
| p | q | p ↔q |
| T | T | T |
| T | F | F |
| F | T | F |
| F | F | T |
- If p denotes “I am at home.” and q denotes “It is raining.” then p ↔q denotes “I am at home if and only if it is raining.”
- Some alternative ways biconditional “p if and only if q” is expressed in English:
- p is necessary and sufficient for q
- if p then q , and conversely
- p iff q
Truth Tables for Compound Propositions: Construction
- Rows
- Need a row for every possible combination of values for the atomic propositions.
- Columns
-
- Need a column for the compound proposition (usually at far right)
- Need a column for the truth value of each expression that occurs in the compound proposition as it is built up.
- This includes the atomic propositions
-
- Construct a truth table for p ∨ q → ¬r
| p | q | r | ¬r | p ∨ q | p ∨ q → ¬r |
| T | T | T | F | T | F |
| T | T | F | T | T | T |
| T | F | T | F | T | F |
| T | F | F | T | T | T |
| F | T | T | F | T | F |
| F | T | F | T | T | T |
| F | F | T | F | F | T |
| F | F | F | T | F | T |
Equivalent Propositions
- Two propositions are equivalent if they always have the same truth value.
- Example: Show using a truth table that the conditional is equivalent to the contrapositive.
- Solution:
| p | q | ¬ p | ¬ q | p →q | ¬q → ¬ p |
| T | T | F | F | T | T |
| T | F | F | T | F | F |
| F | T | T | F | T | T |
| F | F | T | T | T | T |
- p →q is equivalent to ¬q → ¬ p
Using Truth Tables to show Non-Equivalence
- Example: Show using truth tables that neither the converse nor inverse of an implication are equivalent to the implication.
- Solution:
|
p |
q |
¬ p |
¬ q |
p →q |
¬ p →¬ q |
q → p |
|
T |
T |
F |
F |
T |
T |
T |
|
T |
F |
F |
T |
F |
T |
T |
|
F |
T |
T |
F |
T |
F |
F |
|
F |
F |
T |
T |
T |
T |
T |
Considerations for Truth Tables
- How many rows are there in a truth table with n propositional variables?
- Solution: 2n This follows from the fact that each of the n variables can draw from one of two truth values (T or F).
- Note that this also means that with n propositional variables, we can construct 2n distinct (i.e., not equivalent) propositions.
Precedence of Logic Operators
|
Operator |
Precedence |
|
¬ |
1 |
|
∧ ∨ |
2 3 |
|
→ ↔ |
4 5 |
- p ∨q → ¬r is equivalent to (p ∨q) → ¬r
- If the intended meaning is p ∨(q → ¬r ) then parentheses must be used.
Translating English into Propositional Logic
- Steps to convert an English sentence to a statement in propositional logic
- Identify atomic propositions and represent them using propositional variables.
- Determine appropriate logical connectives
- “If I go to Harry’s or to the country, I will not go shopping.”
- p: I go to Harry’s
- q: I go to the country
- r: I will go shopping.
- If p or q then not r.
- Problem: Translate the following sentence into propositional logic:
- “You can access the Internet from campus only if you are a computer science major or you are not a freshman.”
- One Solution: Let a, c, and f represent, respectively, “You can access the internet from campus,” “You are a computer science major,” and “You are a freshman.”
- a = access
- c = cs major
- f = freshman
- Restate as “If you can access the Internet from campus, you are a computer science major, or you are not a freshman”
- a→ (c ∨ ¬ f )
Translating System Specifications into Propositional Logic
- System and Software engineers take requirements in English and express them in a precise specification language based on logic.
- Example: Express in propositional logic:
- “The automated reply cannot be sent when the file system is full”
- Solution: One possible solution: Let p denote “The automated reply can be sent” and q denote “The file system is full.”
- Restate as: “if the file system is full, you cannot send the automated reply”
- q→ ¬ p
Consistent System Specifications
- Definition: A list of propositions is consistent if it is possible to assign truth values to the proposition variables so that each proposition is true. (have to search for truth value that makes them all true)
- Exercise: Are these specifications consistent?
- “The diagnostic message is stored in the buffer or it is retransmitted.”
- p ∨ q
- “The diagnostic message is not stored in the buffer.”
- ¬p
- “If the diagnostic message is stored in the buffer, then it is retransmitted.”
- p → q
- “The diagnostic message is stored in the buffer or it is retransmitted.”
- Solution: Let p denote “The diagnostic message is stored in the buffer.” Let q denote “The diagnostic message is retransmitted” The specification can be written as: p ∨ q, ¬p, p → q. When p is false and q is true all three statements are true. So the specification is consistent.
- What if “The diagnostic message is not retransmitted is added.”
- Solution: Now we are adding ¬q and there is no satisfying assignment. So the specification is not consistent.
Tautologies, Contradictions, and Contingencies
- A tautology is a proposition that is always true.
- Example: p ∨¬p
- A contradiction is a proposition that is always false.
- Example: p ∧¬p
- A contingency is a proposition which is neither a tautology nor a contradiction, such as p
|
P |
¬p |
p ∨¬p (tautology) |
p ∧¬p (contradiction) |
|
T |
F |
T |
F |
|
F |
T |
T |
F |
Logical Equivalence
- Two compound propositions p and q are logically equivalent if p↔q is a tautology.
- We write this as p⇔q or as p≡ q where p and q are compound propositions.
- Two compound propositions p and q are equivalent if and only if the columns in a truth table giving their truth values agree.
- This truth table shows that ¬p ∨ q is equivalent to p → q.
| p | q | ¬p | ¬p ∨ q | p→ q |
| T | T | F | T | T |
| T | F | F | F | F |
| F | T | T | T | T |
| F | F | T | T | T |
DeMorgan’s Laws
- A conjunction (^) negated is the individual not of disjunction
- A disjunction (v) negated is the individual not of conjunction
- This truth table shows that De Morgan’s Second Law holds.
-
p q ¬p ¬q (p∨q) ¬(p∨q) ¬p∧¬q T T F F T F F T F F T T F F F T T F T F F F F T T F T T
Key Logical Equivalences
Constructing New Logical Equivalences
- We can show that two expressions are logically equivalent by developing a series of logically equivalent statements.
- To prove that A== B we produce a series of equivalences beginning with A and ending with B.
- Keep in mind that whenever a proposition (represented by a propositional variable) occurs in the equivalences listed earlier, it may be replaced by an arbitrarily complex compound proposition.
Equivalence Proofs
- Examples of proving tautology or equivalences
Disjunctive Normal Form (DNF)
- A propositional formula is in disjunctive normal form if it consists of a disjunction of (1, … ,n) disjuncts, where each disjunct consists of a conjunction of (1, …, m) atomic formulas or the negation of an atomic formula.
- Yes
- No
- Disjunctive Normal Form is used in applications such as circuit design.
- Example: Show that every compound proposition can be put in disjunctive normal form.
- Solution: Construct the truth table for the proposition. Then an equivalent proposition is the disjunction with n disjuncts (where n is the number of rows for which the formula evaluates to T). Each disjunct has m conjuncts where m is the number of distinct propositional variables. Each conjunct includes the positive form of the propositional variable if the variable is assigned T in that row and the negated form if the variable is assigned F in that row. This proposition is in disjunctive normal from.
- Example: Find the Disjunctive Normal Form (DNF) of
- (p∨q)→¬r
- Solution: This proposition is true when r is false or when both p and q are false.
- (¬ p∧ ¬ q) ∨ ¬r
Conjunctive Normal Form (CNF)
- A compound proposition is in Conjunctive Normal Form (CNF) if it is a conjunction of disjunctions.
- Every proposition can be put in an equivalent CNF.
- Conjunctive Normal Form (CNF) can be obtained by eliminating implications, moving negation inwards and using the distributive and associative laws.
- Important in resolution theorem proving used in artificial Intelligence (AI).
- A compound proposition can be put in conjunctive normal form through repeated application of the logical equivalences covered earlier.
Propositional Satisfiability
- A compound proposition is satisfiable if there is an assignment of truth values to its variables that make it true. When no such assignments exist, the compound proposition is unsatisfiable.
- A compound proposition is unsatisfiable if and only if its negation is a tautology.
eof